A. Technical Field
The present invention is related to information retrieval, and more particularly, to retrieving information about a signal such as a music track or song, and creating a database of signals and the information retrieved about the signals.
B. Background of the Invention
In many contexts retrieving information about a sequence of unknown items is desirable. One such context is music. Some electronic copies of a piece of music include not only the music itself but also a tag (also known as meta-data). The tag includes information about the music such as the artist, the album name, and the track name. The tag can include any other information associated with the music entered by a listener.
However, some electronic copies of songs do not include the tag information. In particular, copies of songs downloaded from Napster or other sites where music can be downloaded only rarely include complete tag information. Additionally, as systems for recognizing music are fielded, it is likely that those providing copyrighted music without license will make efforts to evade any filtering system put into place. This has happened already with systems based on file name filtering. Thus, it is reasonable to expect slight variations of songs to be encountered in which the variations do not change the file substantially for the listener, but might make naïve comparison methods unreliable. Examples of such modifications include slight trimming of the beginning of a song, changes in overall volume, band-limiting and changes in equalization.
One way to replace missing tag information is to compare the waveforms of an unknown song (i.e. one that does include tag information) to those of known songs (i.e. songs for which tag information is known). When two waveforms match, tags can be transferred to unknown song. However, this method is inefficient in time and space because direct wave-form comparison is computationally expensive. Also, music files available over the Internet are usually compressed using a compression algorithm such as MP3. Compression makes direct comparison of audio waveforms impossible since there will, by nature, be significant differences between the original signal and the signal recovered from a lossily compressed version. These differences will not generally be audible, but they can be substantial in magnitude, especially when phase information is discarded by the compression algorithm.
An alternative method of determining tag information is to perform feature comparison rather than waveform comparison. Feature comparison is the comparison of analog features associated with the waveform such as correlating spectra or comparing extracted rhythm signatures. Feature comparison is also slow because it involves comparison of analog features that occur over time. Thus, comparison using these analog features requires exhaustive comparison and time-alignment. Moreover, many analog features are not invariant under common transformations such as translation in time, volume scaling and small changes in equalization.
What is needed is a system and method of determining tag information for an unknown music track that avoids the above-described limitations and disadvantages. What is further needed is a system and method that leads to accurate retrieval of tag information for a compressed, trimmed piece of music of limited bandwidth. What is further needed is a system and method that is efficient in time and memory space. Currently available systems require an exhaustive search and expensive comparisons to each exemplar. Both the exhaustive search and the expensive comparison operations should be avoided if possible.